package 面试;

import java.util.PriorityQueue;

public class 无序数组的中位数 {


    public static int partTion(int[] array, int start, int end) {
        int i = start;
        int j = end + 1;
        int v = array[start];
        while (true) {
            // 在左边找到第一个大于 v 的
            while (array[++i] < v) {
                if (i == end) {
                    break;
                }
            }
            // 在右边找到第一个小于 v 的
            while (v < array[--j]) {
                if (j == start) {
                    break;
                }
            }
            // 检测是否交换结束
            if ( i >= j) {
                break;
            }
            // 交换双方数据
            array[i] ^= array[j];
            array[j] ^= array[i];
            array[i] ^= array[j];
        }
        if (start != j) {
            // 交换 j 与 start 并返回 j
            array[start] ^= array[j];
            array[j] ^= array[start];
            array[start] ^= array[j];
        }
        return j;
    }

    /*
    * 小顶堆解决方案
    * ????? todo 
    * */
    public static void minHeap(int[] a) {
        int n = a.length;
        int m = (n+1)/2;
        PriorityQueue queue = new PriorityQueue(m);
        // 将数组的前 （n+1）/2 个元素构成小顶堆
        for (int i = 0; i < m; i++) {
            queue.add(a[i]);
        }
        // 将剩下的与堆顶元素比较，丢弃小于等于堆顶元素的数据
        for (int i = m; i < n; i++) {
            if ((int)queue.peek() < a[i]) {
                // 取代堆顶元素
                queue.poll();
                queue.add(a[i]);
            }
        }
        System.out.println(queue.peek());
    }

    public static void main(String[] args) {
        int[] array = {6,5,9,8,1,4,2,7,3};
        minHeap(array);
//        int start = 0;
//        int end = array.length-1;
//        int div = partTion(array, start ,end);
//        int mid = (end - 1) / 2;
//        boolean even = true;
//        if ((array.length & 1) == 1) {
//            // 若是奇数个
//             mid = (end + 1) / 2;
//             even = false;
//        }
//        while (mid != div) {
//            if (mid < div) {
//                div = partTion(array, start, div-1);
//            } else {
//                div = partTion(array, div+1, end);
//            }
//        }
//        if (even) {
//            double a = array[array.length / 2];
//            double b = array[array.length / 2 - 1];
//            double c = (a+b) / 2.0;
//            System.out.println(c);
//        } else {
//            System.out.println(array[mid]);
//        }
    }
}
// 奇数：取中间的

// 偶数：取中间两个的平均值